cs144 labs(Winter 2024)
· 31 min read
Lab0
这个lab 纯纯的热身lab, part1是用webget简单进行个请求, 类似csapp的网络lab part1
part2字符串操作, 恶心一点的就是string_view的peek和一个ring buffer不太能兼容, 总之我的代码效率也挺低的就不拿出来献丑了()
Lab1
这个lab要求实现tcp字节流抽象的重组部分Reassembler
调的时候还是很恶心的, 非常多的edge case, 建议好好看测试是怎么构造的
写的时间最久的一个lab, 但这里笔记没有多少, 因为Lab1结束到Lab2开始的两个星期干别的去记不清当时的感受了()
还是放个源代码
#include "reassembler.hh"
<!--truncate-->#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
using namespace std;
void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )
{
// Your code here.
(void)first_index;
(void)data;
(void)is_last_substring;
// NOTE: every byte pushed is valid sequence.
// NOTE: cur index to be pushed might be partially pushed before, so need to check
// NOTE: "That is, you can assume that there is a unique underlying byte-stream, and all
// NOTE: substrings are (accurate) slices of it" ---- package may be lost but not corrupted
// NOTE: buffer: start marker next_index, len is available_capacity
std::cerr << "first_index: " << first_index << " data: " << data << " is_last_substring: " << is_last_substring
<< std::endl;
if ( output_.writer().available_capacity() > buffer.size() ) {
// buffer = string( output_.writer().available_capacity() - buffer.size(), 'x' ) + buffer;
buffer.resize( output_.writer().available_capacity() );
}
// duplicate one, drop
if ( first_index + data.size() < next_index ) {
return;
}
if ( first_index + data.size() == next_index ) {
if ( is_last_substring ) {
output_.writer().close();
clear_buffer();
}
return;
}
// overlap
if ( first_index < next_index ) {
assert( first_index + data.size() > next_index );
data = data.substr( next_index - first_index, output_.writer().available_capacity() );
// add
if ( !data.empty() ) {
// has some space to contain data
write_in_space( data, is_last_substring );
}
return;
}
// gap, exceed capacity
if ( first_index >= next_index + buffer.size() ) {
cerr << "gap: drop package" << endl;
return;
}
// gap, (partially) in capacity, store in buffer
if ( first_index > next_index ) {
if ( first_index + data.size() > next_index + buffer.size() ) {
auto input_size = buffer.size() - ( first_index - next_index );
// NOTE: partial overlap cannot be the last
find_replace_buffer_item( data.substr( 0, input_size ), first_index, false );
} else {
find_replace_buffer_item( data, first_index, is_last_substring );
}
return;
}
// exactly equal, write
assert( first_index == next_index );
// when data.size() < buffer.size(), substr return data
// NOTE: partial overlap cannot be the last
if ( data.size() > buffer.size() ) {
data = data.substr( 0, buffer.size() );
write_in_space( data, false );
} else {
write_in_space( data, is_last_substring );
}
}
uint64_t Reassembler::bytes_pending() const
{
// Your code here.
return bytes_pending_;
}
#pragma once
#include "byte_stream.hh"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <set>
#include <vector>
class Reassembler
{
private:
/**
* @brief cut all items start before index
*/
void rebuild_buffer_items( uint64_t index )
{
int cnt = 0;
for ( const auto& item : buffered_items ) {
if ( item.index + item.size <= index ) {
// NOTE:can be partially overlapped
bytes_pending_ -= item.size;
cnt++;
} else {
break;
}
}
if ( cnt > 0 ) {
buffered_items.erase( buffered_items.begin(), std::next( buffered_items.begin(), cnt ) );
}
}
void clear_buffer()
{
buffered_items.clear();
buffer.resize( 0 );
bytes_pending_ = 0;
next_index = 0;
}
/**
* @brief DO buffer opeartions and capacity check OUTSIDE!!!
* @param data
* @param start
* @param is_last_substring
*/
void find_replace_buffer_item( const std::string& data, uint64_t start, bool is_last_substring )
{
// auto it = find_if( buffered_items.begin(), buffered_items.end(), [start, size]( const auto& item ) {
// return ( item.index <= start && start <= item.size + item.index )
// || ( start <= item.index && item.index <= start + size );
// } );
assert( start > next_index );
auto size = data.size();
buffer.replace( start - next_index, size, data );
buffered_items.emplace( start, size, is_last_substring );
// combine the next item
// NOTE: now the set has been sorted
std::set<SubStringTuple> new_buffer;
uint64_t seg_start = start;
uint64_t seg_end = start + size;
bool seg_is_last = is_last_substring;
for ( const auto& item : buffered_items ) {
if ( item.index + item.size >= seg_start && item.index <= seg_start ) {
seg_start = item.index;
}
if ( item.index <= seg_end && item.size + item.index >= seg_end ) {
seg_end = item.index + item.size;
seg_is_last = item.is_last_substring;
}
}
bytes_pending_ = 0;
for ( const auto& item : buffered_items ) {
if ( item.index + item.size < seg_start || item.index > seg_end ) {
new_buffer.insert( item );
bytes_pending_ += item.size;
}
}
new_buffer.emplace( seg_start, seg_end - seg_start, seg_is_last );
bytes_pending_ += seg_end - seg_start;
buffered_items.clear();
buffered_items = new_buffer;
}
/**
* @brief there has enough space(from next_index) to write data in buffer
* @param data
*/
void write_in_space( const std::string& data, bool is_last_substring )
{
output_.writer().push( data );
buffer = buffer.substr( data.size() );
next_index += data.size();
rebuild_buffer_items( next_index );
bool end = is_last_substring;
while ( !end ) {
auto it = std::find_if( buffered_items.begin(), buffered_items.end(), [this]( const auto& item ) {
return item.index <= next_index && item.index + item.size > next_index;
} );
if ( it == buffered_items.end() ) {
break;
}
assert( it->size > ( next_index - it->index ) );
auto append_len = it->size - ( next_index - it->index );
output_.writer().push( buffer.substr( 0, append_len ) );
buffer = buffer.substr( append_len );
next_index += append_len;
end = it->is_last_substring;
rebuild_buffer_items( next_index );
}
if ( end ) {
clear_buffer();
output_.writer().close();
}
}
public:
// Construct Reassembler to write into given ByteStream.
explicit Reassembler( ByteStream&& output )
: output_( std::move( output ) )
, bytes_pending_( 0 )
, buffered_items()
, buffer( output.writer().available_capacity(), '\0' )
, next_index( 0 )
{}
/*
* Insert a new substring to be reassembled into a ByteStream.
* `first_index`: the index of the first byte of the substring
* `data`: the substring itself
* `is_last_substring`: this substring represents the end of the stream
* `output`: a mutable reference to the Writer
*
* The Reassembler's job is to reassemble the indexed substrings (possibly out-of-order
* and possibly overlapping) back into the original ByteStream. As soon as the Reassembler
* learns the next byte in the stream, it should write it to the output.
*
* If the Reassembler learns about bytes that fit within the stream's available capacity
* but can't yet be written (because earlier bytes remain unknown), it should store them
* internally until the gaps are filled in.
*
* The Reassembler should discard any bytes that lie beyond the stream's available capacity
* (i.e., bytes that couldn't be written even if earlier gaps get filled in).
*
* The Reassembler should close the stream after writing the last byte.
*/
void insert( uint64_t first_index, std::string data, bool is_last_substring );
// How many bytes are stored in the Reassembler itself?
uint64_t bytes_pending() const;
// Access output stream reader
Reader& reader() { return output_.reader(); }
const Reader& reader() const { return output_.reader(); }
// Access output stream writer, but const-only (can't write from outside)
const Writer& writer() const { return output_.writer(); }
struct SubStringTuple
{
uint64_t index;
uint64_t size;
bool is_last_substring;
bool operator<( const SubStringTuple& rhs ) const
{
return index < rhs.index || ( index == rhs.index && size < rhs.size );
}
void setIndex( uint64_t i ) { this->index = i; }
void setSize( uint64_t s ) { this->size = s; }
void setLast( bool l ) { this->is_last_substring = l; }
};
uint64_t get_next_index() const { return next_index; }
// auto get_remain_capacity() const { return buffer.size(); };
private:
ByteStream output_; // the Reassembler writes to this ByteStream
uint64_t bytes_pending_; // number of bytes stored in the Reassembler itself
std::set<SubStringTuple> buffered_items;
std::string buffer;
uint64_t next_index;
};
Lab2
这个lab要求实现一个TCP receiver, 并和Lab1之中的Reassembler对接, 将发过来的一系列tcp包解开并处理字节流
面向测试编程最爽的一集
不如说这个lab就是在展示一个丰富的测试应该是什么样子的(15行代码上千行测试(雾))
代码逻辑很简单,但测试之丰富让你必须考虑所有的edge case
part1 是处理TCP协议之中, SeqNo是用32位整数存, 具有4G的上限(并且还要考虑到随机初始的ISN来防止攻击, 实际可用还不到4G),但我们的网络肯定不能只能最多传4G数据,所以我们的底层用的是uint64_t, 就带来了从32位的SeqNo和初始的32位ISN转到64位的,用于reassamble的64位绝对seqNo, 采用的是一个"零点+游标"的方法, ISN就是零点,而使用已有的下一个绝对SeqNo作为参考的游标以避免多值性, 从SeqNo和ISN的"差值"可以得到实际上64位的绝对index的低32位, 而高位是进位还是退位还是不变则根据游标决定.
我的代码如下, 感觉其实是写复杂了, 但思路还是清晰的
Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point )
{
// Your code here.
(void)n;
(void)zero_point;
return zero_point + static_cast<uint32_t>( n );
}
uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const
{
// Your code here.
(void)zero_point;
(void)checkpoint;
uint32_t mask = 0xFFFFFFFF;
uint32_t cp_low = checkpoint & mask;
uint32_t diff = 0;
if ( this->raw_value_ > zero_point.raw_value_ ) {
diff = this->raw_value_ - zero_point.raw_value_;
} else {
uint32_t gap = zero_point.raw_value_ - this->raw_value_;
diff = 0xFFFFFFFF - gap + 1;
}
// std::cout << "cp_low:" << cp_low << " ,diff:" << diff << ",checkpoint:" << checkpoint << std::endl;
if ( diff > cp_low ) {
if ( diff - cp_low < 0x80000000 ) {
return checkpoint - cp_low + diff;
} else {
uint64_t a = static_cast<uint64_t>( 0x80000000 ) << 1;
// HINT: a "less than 0" abs seqNo means nothing
return checkpoint - cp_low + diff > a ? checkpoint - cp_low + diff - a : checkpoint - cp_low + diff;
}
} else {
if ( cp_low - diff < 0x80000000 ) {
return checkpoint - cp_low + diff;
} else {
return checkpoint - cp_low + diff + ( static_cast<uint64_t>( 0x80000000 ) << 1 );
}
}
}
在part2之中, TCP receiver需要传给lab1之中写好的reassembler index数据
这里的index又是字节流的index, 和我们abs SeqNo又有差别:
- SYN, FIN这种包是可以带一个空data的, 并且这些占据了SeqNo的包可以写入数据流(如果不带data)
- SYN, FIN这种标志位是可以共存的, 虽然这不是一个标准TCP行为, 但可以是对方的bug, 也可以是魔改协议, 硬件上并没有对共存性做校验, 本机需要能处理, 典型的如 SYN+data+FIN
- RST的处理是简化的, 文档对RST的说明并不详细, 测试中就是简单的
RST bit <-> Stream Error, 查询了一下资料, 以下情况 都可以产生RST- 目的地为某端口的
SYN到达，然而在该端口上并没有正在监听的服务器； - TCP想取消一个已有连接；(异常中止等, 此时会丢弃已有的一些信息, 如缓冲区数据, 又比如TCP保活机制+检测到对方不可达)
- TCP接收到一个根本不存在的连接上的分节。(例如已经关闭又收到)
- 目的地为某端口的
除了index和abs SeqNo转换,还有就是window size的设置(依赖于可用空间的检测)和ISN的设置, RST的处理, 最后的代码如下
#include "tcp_receiver.hh"
#include "tcp_sender_message.hh"
#include "wrapping_integers.hh"
#include <cstdint>
using namespace std;
void TCPReceiver::receive( TCPSenderMessage message )
{
// Your code here.
(void)message;
if ( message.SYN ) {
isn_ = Wrap32( message.seqno );
}
if ( message.RST ) {
reassembler_.reader().set_error();
}
if ( !isn_ ) {
return;
}
uint64_t checkpoint = reassembler_.get_next_index();
// 1: SYN
uint64_t data_index = message.seqno.unwrap( isn_.value(), checkpoint ) + message.SYN - 1;
reassembler_.insert( data_index, message.payload, message.FIN );
}
TCPReceiverMessage TCPReceiver::send() const
{
// Your code here.
// return {};
TCPReceiverMessage msg;
msg.window_size = reassembler_.writer().available_capacity() > UINT16_MAX
? UINT16_MAX
: reassembler_.writer().available_capacity();
// +1: SYN seqNo
if ( reassembler_.writer().has_error() ) {
msg.RST = true;
}
if ( !isn_.has_value() ) {
return msg;
}
msg.ackno
= Wrap32::wrap( reassembler_.writer().bytes_pushed() + 1 + reassembler_.writer().is_closed(), isn_.value() );
return msg;
}
Lab3
这个lab要求实现发送端TCP Sender, 主要是对根据window size等进行分包装包并发送
有一说一, 文档虽然挺详细了, 但有地方还是不是很清楚
基本上几个函数里面怎么写文档里都讲了
放个个人实现吧
可能需要注意的是几个地方:
TCPConfig::MAX_PAYLOAD_SIZE只计算data的payload, SYN,FIN不计算在里面- 如果有刚好放不下FIN的, 按照测试的想法是需要在下一次push传, 不能等待tick重传等
- 和上面"刚好放不下"对应, receive可以接收一个不变的seqNo, 但window size改变, 需要注意到这一点并处理
- 同时, 根据测试得, receive对传入的seqno做校验, 但不对window size做校验, 也就是改变window size和seqNo怎么样没有关系, 其实细想也是合理的, 测试给了一种情况就是在连接开始时receive了一个seqNo为空, 但改变window size
- 不用担心RST, 这里基本没有对它进行严格测试
- 注意文档里面写的 window size为0 的特殊情况仅在push中成立, 并且特殊情况也只是改变window size而不是始终有1的容量发(中间占了就不行)
make_empty_message()只是测试用的, 设置好seqno就行- 多注意测试中什么时候push和close管道了
#include "tcp_sender.hh"
#include "byte_stream.hh"
#include "tcp_config.hh"
#include "tcp_sender_message.hh"
#include "wrapping_integers.hh"
#include <algorithm>
#include <cassert>
#include <iostream>
using namespace std;
uint64_t TCPSender::sequence_numbers_in_flight() const
{
// Your code here.
return next_send_segno - received_max_ackno;
}
uint64_t TCPSender::consecutive_retransmissions() const
{
// Your code here.
return timer.get_consecutive_retransmissions();
}
void TCPSender::push( const TransmitFunction& transmit )
{
// Your code here.
uint64_t has_pushed = 0;
bool finished = false;
std::cerr << "--- Push Start" << std::endl;
if ( finish_send ) {
return;
}
if ( input_.reader().is_finished() && !finish_send && sequence_numbers_in_flight() < cur_window_size ) {
// HINT: extra fin not send
cerr << "extra fin" << endl;
auto msg = make_empty_message();
msg.FIN = true;
if ( next_send_segno == 0 ) {
msg.SYN = true;
}
outstanding_segs.push( { next_send_segno, msg } );
next_send_segno += msg.sequence_length();
finish_send = true;
transmit( msg );
return;
}
if ( !timer.is_active() ) {
timer.start();
}
// HINT: window size == 0 's push special case
auto fake_window_size = cur_window_size == 0 ? 1 : cur_window_size;
auto cur_space
= fake_window_size > sequence_numbers_in_flight() ? fake_window_size - sequence_numbers_in_flight() : 0;
while ( has_pushed < cur_space && !finished ) {
TCPSenderMessage msg;
if ( next_send_segno == 0 ) {
msg.SYN = true;
}
if ( input_.has_error() ) {
msg.RST = true;
}
if ( cur_space - has_pushed > TCPConfig::MAX_PAYLOAD_SIZE + msg.SYN ) {
// NOTE: window space > payload
uint16_t pkg_sz = TCPConfig::MAX_PAYLOAD_SIZE;
read( input_.reader(), pkg_sz, msg.payload );
if ( input_.reader().is_finished() ) {
msg.FIN = true;
}
} else {
// NOTE: window limit seqno gap instead of actual payload bytes
uint16_t pkg_sz = cur_space - has_pushed - msg.SYN;
if ( input_.reader().bytes_buffered() < pkg_sz ) {
read( input_.reader(), input_.reader().bytes_buffered(), msg.payload );
msg.FIN = input_.reader().is_finished();
} else {
// HINT:for == case, FIN can't be send during this push. The **test points** that it should be pushed in
// next call of push() if window has enough space (instead of placing it in outstanding segments or other
// solutions)
read( input_.reader(), pkg_sz, msg.payload );
}
}
if ( msg.FIN ) {
finished = true;
finish_send = true;
}
msg.seqno = Wrap32( isn_ + next_send_segno );
if ( msg.sequence_length() == 0 ) {
// nothing to send
break;
}
// update outstanding
outstanding_segs.push( { next_send_segno, msg } );
// update next_send
next_send_segno += msg.sequence_length();
std::cerr << "Send: " << msg << std::endl;
// send msg
transmit( msg );
has_pushed += msg.sequence_length();
}
std::cerr << "--- Push End" << std::endl;
}
TCPSenderMessage TCPSender::make_empty_message() const
{
// Your code here.
TCPSenderMessage msg;
msg.seqno = Wrap32( isn_ + next_send_segno );
msg.RST = input_.has_error();
return msg;
}
void TCPSender::receive( const TCPReceiverMessage& msg )
{
// Your code here.
(void)msg;
if ( msg.RST ) {
this->writer().set_error();
timer.reset_all();
while ( !outstanding_segs.empty() )
outstanding_segs.pop();
}
if ( msg.ackno.has_value() ) {
uint64_t abs_seq = msg.ackno->unwrap( this->isn_, writer().bytes_pushed() );
// HINT: check if valid
if ( abs_seq > received_max_ackno && abs_seq <= next_send_segno ) {
// fully received, remove it
while ( !outstanding_segs.empty()
&& outstanding_segs.top().abs_seq + outstanding_segs.top().msg.sequence_length() <= abs_seq ) {
std::cerr << "Receive: " << outstanding_segs.top().msg << std::endl;
outstanding_segs.pop();
}
received_max_ackno = abs_seq;
timer.reset_all();
timer.start();
}
}
// HINT: not validate the window size change
cerr << "change window size to: " << msg.window_size << endl;
cur_window_size = msg.window_size;
}
void TCPSender::tick( uint64_t ms_since_last_tick, const TransmitFunction& transmit )
{
// Your code here.
(void)ms_since_last_tick;
(void)transmit;
bool expired = timer.update( ms_since_last_tick );
if ( !expired ) {
// cerr << "Not expired" << endl;
return;
}
// retransmit earliest seg
if ( !outstanding_segs.empty() ) {
auto [_, msg] = outstanding_segs.top();
transmit( msg );
std::cerr << "Retransmit: " << msg << std::endl;
if ( cur_window_size != 0 ) {
// i. keep track of retransmission
timer.add_consecutive_retransmissions();
// ii. double the RTO and restart the timer
timer.set_rto( 2 * timer.get_rto() );
cerr << "Doubled RTO with window size " << cur_window_size << endl;
}
// reset the time and start
timer.clear_timer();
timer.start();
}
}
#pragma once
#include "byte_stream.hh"
#include "retransmit_timer.hh"
#include "tcp_receiver_message.hh"
#include "tcp_sender_message.hh"
#include "wrapping_integers.hh"
#include <cstdint>
#include <functional>
#include <list>
#include <memory>
#include <optional>
#include <ostream>
#include <queue>
class TCPSender
{
public:
/* Construct TCP sender with given default Retransmission Timeout and possible ISN */
TCPSender( ByteStream&& input, Wrap32 isn, uint64_t initial_RTO_ms )
: input_( std::move( input ) )
, isn_( isn )
, outstanding_segs()
, received_max_ackno( 0 )
, next_send_segno( 0 )
, cur_window_size( 1 )
, timer( initial_RTO_ms )
, finish_send( false )
{}
/* Generate an empty TCPSenderMessage */
TCPSenderMessage make_empty_message() const;
/* Receive and process a TCPReceiverMessage from the peer's receiver */
void receive( const TCPReceiverMessage& msg );
/* Type of the `transmit` function that the push and tick methods can use to send messages */
using TransmitFunction = std::function<void( const TCPSenderMessage& )>;
/* Push bytes from the outbound stream */
void push( const TransmitFunction& transmit );
/* Time has passed by the given # of milliseconds since the last time the tick() method was called */
void tick( uint64_t ms_since_last_tick, const TransmitFunction& transmit );
// Accessors
uint64_t sequence_numbers_in_flight() const; // How many sequence numbers are outstanding?
uint64_t consecutive_retransmissions() const; // How many consecutive *re*transmissions have happened?
Writer& writer() { return input_.writer(); }
const Writer& writer() const { return input_.writer(); }
// Access input stream reader, but const-only (can't read from outside)
const Reader& reader() const { return input_.reader(); }
private:
// Variables initialized in constructor
ByteStream input_;
Wrap32 isn_;
struct outstanding_pair
{
uint64_t abs_seq;
TCPSenderMessage msg;
// priority less, abs_seq greater
bool operator<( const outstanding_pair& rhs ) const { return abs_seq > rhs.abs_seq; }
};
std::priority_queue<outstanding_pair> outstanding_segs;
uint64_t received_max_ackno;
uint64_t next_send_segno;
uint64_t cur_window_size;
RetransmitTimer timer;
bool finish_send;
};
#pragma once
#include <stdexcept>
#include <stdint.h>
class RetransmitTimer
{
uint64_t cur_timer_ms_;
uint64_t consecutive_retransmissions;
const uint64_t initial_RTO_ms_;
uint64_t cur_RTO_ms_;
bool active;
public:
RetransmitTimer( uint64_t initial_RTO_ms )
: cur_timer_ms_( 0 )
, consecutive_retransmissions( 0 )
, initial_RTO_ms_( initial_RTO_ms )
, cur_RTO_ms_( initial_RTO_ms )
, active( false )
{}
uint64_t get_time_ms_() const { return cur_timer_ms_; }
// return if expired
bool update( uint64_t ms_since_last_tick )
{
if ( !active ) {
throw std::runtime_error( "try to update when timer is not active" );
}
cur_timer_ms_ += ms_since_last_tick;
return cur_timer_ms_ >= cur_RTO_ms_;
}
void start() { active = true; }
void stop() { active = false; }
// getter & setter
uint64_t get_rto() { return cur_RTO_ms_; }
uint64_t get_init_rto() const { return initial_RTO_ms_; }
uint64_t get_consecutive_retransmissions() const { return consecutive_retransmissions; }
void set_rto( uint64_t rto ) { cur_RTO_ms_ = rto; }
void clear_timer()
{
cur_timer_ms_ = 0;
active = false;
}
void set_consecutive_retransmissions( uint64_t num ) { consecutive_retransmissions = num; }
void add_consecutive_retransmissions() { consecutive_retransmissions++; }
void reset_rto() { cur_RTO_ms_ = initial_RTO_ms_; }
void reset_all()
{
cur_RTO_ms_ = initial_RTO_ms_;
consecutive_retransmissions = 0;
cur_timer_ms_ = 0;
active = false;
}
bool is_active() const { return active; }
};
Lab4
这个lab要求把前面的组合起来, 测试一下Lab1-3构建的tcp stack能不能正常工作, 替换Lab0中的TCPStack为自己的native版本
checkpoint4好像测不了
一方面不是很确定它这个tun脚本在我的电脑上的兼容性, 另一方面webget他的网站是墙的( , 跑测试全是重传重传
看文档下面可以有./build/tcp_ipv4和./build/tcp_native可以装模作样的自己连自己, 我反正能连通就当是跑通了(乐)
关于他的TUN源码阅读: TODO
Lab5
这个lab要求实现IP层之中的ARP(Address Resolution Protocol)的简化版本, 包括收发消息和超时删除等, 但对于一些现实之中的其他机制(例如超时重发和ICMP回信没有要求)
看懂了他的代码之后这个lab就很简单了, 主要他已经把辅助函数都写完了(这个parse和serialize的实现确实很漂亮, 也算是展示了cpp之中的Duck Type怎么做), 再加上非常详细的文档和注释还有可以作为注释直接读的源代码
也没什么要注意的地方, 唯一可以注意下的是在recv_frame 之中, 只更新sender的ip, ethernet_addr对, 不管target的
贴个代码
//......
private:
// ......
std::vector<std::pair<InternetDatagram, Address>> datagrams_to_send_ {};
std::map<Address, std::pair<EthernetAddress, uint64_t>> arp_table_;
std::map<Address, std::optional<uint64_t>> arp_time_table_;
uint64_t now_;
};
#include <iostream>
#include <optional>
#include <stdexcept>
#include <utility>
#include "address.hh"
#include "arp_message.hh"
#include "ethernet_frame.hh"
#include "ethernet_header.hh"
#include "exception.hh"
#include "ipv4_datagram.hh"
#include "network_interface.hh"
#include "parser.hh"
using namespace std;
//! \param[in] ethernet_address Ethernet (what ARP calls "hardware") address of the interface
//! \param[in] ip_address IP (what ARP calls "protocol") address of the interface
NetworkInterface::NetworkInterface( string_view name,
shared_ptr<OutputPort> port,
const EthernetAddress& ethernet_address,
const Address& ip_address )
: name_( name )
, port_( notnull( "OutputPort", move( port ) ) )
, ethernet_address_( ethernet_address )
, ip_address_( ip_address )
, arp_table_()
, arp_time_table_()
, now_( 0 )
{
cerr << "DEBUG: Network interface has Ethernet address " << to_string( ethernet_address ) << " and IP address "
<< ip_address.ip() << "\n";
}
//! \param[in] dgram the IPv4 datagram to be sent
//! \param[in] next_hop the IP address of the interface to send it to (typically a router or default gateway, but
//! may also be another host if directly connected to the same network as the destination) Note: the Address type
//! can be converted to a uint32_t (raw 32-bit IP address) by using the Address::ipv4_numeric() method.
void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )
{
// Your code here.
(void)dgram;
(void)next_hop;
if ( next_hop != ip_address_ && !arp_table_.contains( next_hop ) ) {
cout << "Wait " << next_hop.to_string() << " for arp response" << endl;
// ARP broadcast
if ( !arp_time_table_.contains( next_hop ) ) {
arp_time_table_[next_hop] = std::nullopt;
}
if ( arp_time_table_[next_hop].has_value() && now_ - arp_time_table_[next_hop].value() < 5000 ) {
// < 5s from last arp broadcast
datagrams_to_send_.push_back( { dgram, next_hop } ); // wait for arp table update and send.
return;
}
// arp broadcast
arp_time_table_[next_hop] = now_;
EthernetHeader header { .dst = ETHERNET_BROADCAST, .src = ethernet_address_, .type = EthernetHeader::TYPE_ARP };
ARPMessage msg { .opcode = ARPMessage::OPCODE_REQUEST,
.sender_ethernet_address = ethernet_address_,
.sender_ip_address = ip_address_.ipv4_numeric(),
.target_ip_address = next_hop.ipv4_numeric() };
auto payload = serialize<ARPMessage>( msg );
EthernetFrame frame { .header = header, .payload = payload };
datagrams_to_send_.push_back( { dgram, next_hop } ); // wait for arp table update and send.
output().transmit( *this, frame );
return;
}
EthernetAddress dst_ethernet_addr;
if ( next_hop == ip_address_ ) {
dst_ethernet_addr = ethernet_address_;
} else {
dst_ethernet_addr = arp_table_.at( next_hop ).first;
}
// cout << "send datagram to " << next_hop.to_string() << " with ethernet address " << to_string(
// dst_ethernet_addr )
// << endl;
EthernetHeader header { .dst = dst_ethernet_addr, .src = ethernet_address_, .type = EthernetHeader::TYPE_IPv4 };
auto payload = serialize<InternetDatagram>( dgram );
EthernetFrame frame { .header = header, .payload = payload };
output().transmit( *this, frame );
}
//! \param[in] frame the incoming Ethernet frame
void NetworkInterface::recv_frame( const EthernetFrame& frame )
{
// Your code here.
(void)frame;
if ( frame.header.dst != ethernet_address_ && frame.header.dst != ETHERNET_BROADCAST ) {
return;
}
// cout << "recv frame" << endl;
bool ok = false;
if ( frame.header.type == EthernetHeader::TYPE_IPv4 ) {
InternetDatagram received_ipv4;
ok = parse<InternetDatagram>( received_ipv4, frame.payload );
if ( ok ) {
datagrams_received_.push( received_ipv4 );
}
} else if ( frame.header.type == EthernetHeader::TYPE_ARP ) {
ARPMessage received_arp;
ok = parse<ARPMessage>( received_arp, frame.payload );
if ( !ok ) {
std::cerr << "Incorrect arp message" << std::endl;
}
Address sender_ip = Address::from_ipv4_numeric( received_arp.sender_ip_address );
arp_table_.insert( std::make_pair( sender_ip, std::make_pair( received_arp.sender_ethernet_address, now_ ) ) );
arp_time_table_.insert( { sender_ip, now_ } );
// cout << "update " << ip_address_.ip() << "'s table from arp response: " << sender_ip.ip() << " -> "
// << to_string( received_arp.sender_ethernet_address ) << endl;
// cout << "Waiting datagrams: " << datagrams_to_send_.size() << endl;
for ( auto it = datagrams_to_send_.begin(); it != datagrams_to_send_.end(); ) {
// cout << "check " << ip.to_string() << endl;
auto [d, ip] = *it;
if ( sender_ip == ip ) {
// std::cerr << "send " << ip.ipv4_numeric() << std::endl;
send_datagram( d, ip );
it = datagrams_to_send_.erase( it );
} else {
it++;
}
}
if ( received_arp.opcode == ARPMessage::OPCODE_REQUEST
&& received_arp.target_ip_address == ip_address_.ipv4_numeric() ) {
ARPMessage respond;
respond.target_ethernet_address = received_arp.sender_ethernet_address;
respond.target_ip_address = received_arp.sender_ip_address;
respond.sender_ip_address = ip_address_.ipv4_numeric();
respond.sender_ethernet_address = ethernet_address_;
respond.opcode = ARPMessage::OPCODE_REPLY;
EthernetHeader respond_header {
.dst = respond.target_ethernet_address, .src = ethernet_address_, .type = EthernetHeader::TYPE_ARP };
EthernetFrame respond_frame { .header = respond_header, .payload = serialize<ARPMessage>( respond ) };
output().transmit( *this, respond_frame );
}
} else {
throw std::runtime_error( "Not Implemented" );
}
}
//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void NetworkInterface::tick( const size_t ms_since_last_tick )
{
// Your code here.
(void)ms_since_last_tick;
now_ += ms_since_last_tick;
cout << "tick " << ms_since_last_tick << endl;
for ( auto it = arp_table_.begin(); it != arp_table_.end(); ) {
if ( now_ - it->second.second >= 30000 ) {
// expired
for ( auto to_send_it = datagrams_to_send_.begin(); to_send_it != datagrams_to_send_.end(); ) {
if ( to_send_it->second == it->first ) {
to_send_it = datagrams_to_send_.erase( to_send_it );
} else {
to_send_it++;
}
}
it = arp_table_.erase( it );
} else {
it++;
}
}
}
Lab6
这个lab要在lab5的基础上写个router(不包括建表算法, 假设表已经建好, 写follow表的部分)
有一个大坑
这个transmit之后做检查在模拟网络里面是立即发生的事情而不是一个"异步操作", 所以如果先transmit, 再修改本地, 比如这样
output().transmit( *this, frame );
datagrams_to_send_.push_back( { dgram, next_hop } ); // wait for arp table update and send.
在checkpoint5之中没有任何问题, 但在checkpoint6之中就会一直判断datagrams_to_send_是空, 从而一直报not received
(也就是transmit了arp req, 再返回了 arp res, 此时等待的datagrams还没有被更新)
还有几个我掉进去的坑点
一个是 datagrams_received()返回的引用如果直接用auto接, auto接引用会转换成副本, 后面就会出错, 并且极其难de
另一个是一个interface下可以有多个host, 所以在存的时候需要把同一个rule下的不同的next_hop存好,而不是直接insert
其实开始的时候我一直没搞清楚为啥摆了一个void route(void) , 我的想法总是void route(const InternetDatagram& dgram)
后来才想明白他是要对receive的数据包做处理, 每一个NetworkInterface就等效于router的一个出入口, 而不是某种终端, 所以收包之后需要过路由
There’s a beauty (or at least a successful abstraction) in the Internet’s design here: the router never thinks about TCP, about ARP, or about Ethernet frames. The router doesn’t even know what the link layer looks like. The router only thinks about Internet datagrams, and only interacts with the link layer through the NetworkInterface abstraction. When it comes to questions like, “How are link-layer addresses resolved?” or “Does the link layer even have its own addressing scheme distinct from IP?” or “What’s the format of the link-layer frames?” or “What’s the meaning of the datagram’s payload?”, the router just doesn’t care.
这里相当于软件上轮询每个接口模拟一个硬件上的收包
代码倒是很简单, 毕竟没要求前缀树之类, 就直接简单化了
#include "router.hh"
#include "address.hh"
#include "ipv4_datagram.hh"
#include <algorithm>
#include <iostream>
#include <optional>
#include <stdexcept>
using namespace std;
bool Router::match( uint32_t address, const RuleKey& r ) const
{
if ( r.len > 32 ) {
throw std::runtime_error( "Invalid len" );
}
uint32_t mask = 0xFFFFFFFF;
for ( int i = 0; i < 32 - r.len; ++i ) {
mask <<= 1;
}
// cout << "DEBUG: mask: " << mask << "Rule: " << r.rule << endl;
return ( address & mask ) == ( r.rule & mask );
}
// route_prefix: The "up-to-32-bit" IPv4 address prefix to match the datagram's destination address against
// prefix_length: For this route to be applicable, how many high-order (most-significant) bits of
// the route_prefix will need to match the corresponding bits of the datagram's destination address?
// next_hop: The IP address of the next hop. Will be empty if the network is directly attached to the router (in
// which case, the next hop address should be the datagram's final destination).
// interface_num: The index of the interface to send the datagram out on.
void Router::add_route( const uint32_t route_prefix,
const uint8_t prefix_length,
const optional<Address> next_hop,
const size_t interface_num )
{
cerr << "DEBUG: adding route " << Address::from_ipv4_numeric( route_prefix ).ip() << "/"
<< static_cast<int>( prefix_length ) << " => " << ( next_hop.has_value() ? next_hop->ip() : "(direct)" )
<< " on interface " << interface_num << "\n";
// Your code here.
_rules[{ route_prefix, prefix_length }].interface_num = interface_num;
_rules[{ route_prefix, prefix_length }].next_hop.push_back( next_hop );
}
// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
void Router::route()
{
// Your code here.
// cout << "DEBUG: routing from " << _rules.size() << "rules and " << _interfaces.size() << " interfaces" << endl;
for ( auto interface : _interfaces ) {
// NOTE: & is important
auto& queue = interface->datagrams_received();
while ( !queue.empty() ) {
auto datagram = queue.front();
cout << interface->name() << " received datagram " << datagram.header.to_string() << endl;
cout << endl << endl;
queue.pop();
if ( datagram.header.ttl <= 1 ) {
continue;
}
// decrease ttl and re-calculate the checksum
datagram.header.ttl--;
datagram.header.compute_checksum();
// route: find the interface to send next
RuleKey target_key = {};
RuleValue target_value = {};
target_key.len = 0;
bool found = false;
// for ( const auto& r : _rules ) {
// cout << r.to_string() << endl;
// }
for ( const auto& r : _rules ) {
// NOTE: =, len = 0, 0.0.0.0/0
if ( match( datagram.header.dst, r.first ) && r.first.len >= target_key.len ) {
target_key = r.first;
target_value = r.second;
found = true;
}
} // 这里显然不需要这个循环, 但for simply first
if ( !found ) {
continue;
}
cout << Address::from_ipv4_numeric( datagram.header.dst ).ip()
<< " matched ip: " << Address::from_ipv4_numeric( target_key.rule ).ip() << endl;
// cout << "found" << endl;
auto send_interface = this->interface( target_value.interface_num );
auto next_hops = target_value.next_hop;
for ( const auto& hop : next_hops ) {
if ( !hop.has_value() ) {
send_interface->send_datagram( datagram, Address::from_ipv4_numeric( datagram.header.dst ) );
break;
}
send_interface->send_datagram( datagram, hop.value() );
}
}
}
}
Lab7
没有队友, 也不能用144的服务器, 测不了, 过